ยินดีต้อนรับสู่บทเรียนที่ 3 ของ แนวคิดเกี่ยวกับปัญญาประดิษฐ์ (PolyU COMP5511). ในเซสชันนี้ เราจะเปลี่ยนจากการค้นหาเส้นทางของเอเจนต์เดี่ยวไปสู่ การค้นหาแบบปรปักษ์, ซึ่งเอเจนต์จะทำงานในสภาพแวดล้อมที่มีหลายเอเจนต์แข่งขันกันกัน เราจะแนะนำ ปัญหาการตอบสนองเงื่อนไข (CSPs), ซึ่งเป็นกระบวนทัศน์ที่เป้าหมายคือการค้นหาสถานะที่ตรงตามข้อจำกัดเฉพาะ แทนที่จะเป็นเส้นทาง

แนวคิดหลัก

• การค้นหาแบบปรปักษ์: มุ่งเน้นไปที่อัลกอริทึมเช่น Minimax และ Alpha-Beta Pruning เพื่อทำการตัดสินใจอย่างมีเหตุผลต่อคู่ต่อสู้ที่ฉลาด
• Monte Carlo Tree Search (MCTS): สำรวจการตัดสินใจเชิงความน่าจะเป็น ซึ่งเป็นแกนหลักสำหรับ AI เกมสมัยใหม่ เช่น AlphaGo.
• การตอบสนองเงื่อนไข: แบบจำลองปัญหาโดยใช้ตัวแปร โดเมน และเงื่อนไข แก้ไขโดย Backtracking และ Local Search.

การวิเคราะห์ความซับซ้อน

ในการตั้งค่าแบบปรปักษ์ ความซับซ้อนของพื้นที่การค้นหามักถูกกำหนดโดยค่า branching factor ของเกม $b$ และความลึก $d$, นำไปสู่ต้นทุนการคำนวณ: $$O{b}^d$$ การเติบโตแบบทวีคูณนี้ต้องการกลยุทธ์การตัดแต่งที่มีประสิทธิภาพ เช่น Alpha-Beta Pruning